package main

import (
	"fmt"
)


type Object interface {}

type Node struct {
	Data Object		// 数据域
	Next *Node		// 下个节点的地址

}

type List struct {
	headNode *Node		// 头节点
}

// 判断是否为空链表
func (list *List) IsEmpty() bool {
	if list.headNode == nil {		// 判断头部节点是否为空即可
		return true
	} else {
		return false
	}
}

// 获取列表长度
func (list *List) Length() int {
	// 获取链表头部节点
	cur := list.headNode
	// 计数器
	count := 0

	for cur != nil {
		// 开始计数
		count++
		// 移动指针进行遍历
		cur = cur.Next
	}

	return count
}

// 从头部添加一个节点
func (list *List) Add(data Object) *Node {
	// 创建一个新的节点, 并通过data进行赋值
	node := &Node{Data: data}
	node.Next = list.headNode
	list.headNode = node

	return node
}

// 从尾部添加节点
func (list *List) Append(data Object) {
	node := &Node{Data: data}

	if list.IsEmpty() {
		// 如果是空的则加为头节点
		list.headNode = node
	} else {
		// 反之追加到尾部
		cur := list.headNode
		for cur.Next != nil {
			cur = cur.Next		// 进行位移遍历链表
		}
		cur.Next = node			// 在最后一个节点的next 指向新节点
	}
}

// 从指定位置添加节点, list.headNode 的index = 0
func (list *List) Insert(index int, data Object) {
	if index < 0 {	// 如果index 小于0, 则从头部插入
		list.Add(data);
	} else if index > list.Length() {	// 如果index 大于链表长度, 则从尾部插入
		list.Append(data)
	} else {
		pre := list.headNode
		count := 0
		for count < (index - 1) {		// 控制在index 位置的前一个节点
			pre = pre.Next
			count++
		}
		// 循环结束, count 是pre指向 index - 1 的位置
		node := &Node{Data: data}
		node.Next = pre.Next		// 将新节点的next 指向 当前pre 的next
		pre.Next = node				// 将pre的next 指向新的节点, 从而实现节点添加
	}
}

// 删除链表指定值的节点
func (list *List) Remove(data Object) {
	pre := list.headNode	// 定义pre. 存储头部节点
	if pre.Data == data {
		list.headNode = pre.Next		// 如果头部节点是要删除的数据那么, 将链表头部节点的下个节点设为头部节点
	} else {	// 如果删除的不是头部节点
		for pre.Next != nil {		// 遍历链表到最后一个节点, 并进行如下判断
			if pre.Next.Data == data {		// 如果pre.Next 的数据是要删除的数据, 那么删除该节点, 并将pre.Next 指向该节点之后的节点
				pre.Next = pre.Next.Next
			} else {			// 如果pre.Next 的数据不是要删除的数据, 那么进行节点位移
				pre = pre.Next
			}
		}
	}
}

// 删除链表指定位置的节点
func (list *List) RemoveAtIndex(index int) {
	pre := list.headNode
	if index <= 0 {
		list.headNode = pre.Next
	} else if index > list.Length() {
		fmt.Println("超出链表长度")
		return
	} else {
		count := 0
		for count != (index - 1) && pre.Next != nil {		// 如果 index -1 == count 那么则跳出循环并删除, 否则将进行遍历位移
			count++
			pre = pre.Next
		}
		pre.Next = pre.Next.Next
	}
}

// 判断链表中是吧包含某个元素
func (list *List) Contain(data Object) bool {
	cur := list.headNode
	for cur.Next != nil {
		if cur.Data == data {
			return true
		}
		cur = cur.Next
	}
	return false
}

// 遍历链表
func (list *List) ShowList() {
	if !list.IsEmpty() {
		cur := list.headNode
		for {
			fmt.Printf("\t%v", cur.Data)
			if cur.Next != nil {
				cur = cur.Next
			} else {
				break
			}
		}
	}
}

